﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
using namespace std;

//NC1 大数加法
//https://www.nowcoder.com/practice/11ae12e8c6fe48f883cad618c2e81475?tpId=196&tqId=37176&ru=/exam/oj

//class Solution {
//public:
//    string solve(string s, string t) {
//        string ret;
//        auto it1 = s.rbegin(), it2 = t.rbegin();
//
//        int next = 0;
//        while (it1 != s.rend() && it2 != t.rend())
//        {
//            int num1 = *it1 - '0', num2 = *it2 - '0';
//            int num = num1 + num2 + next;
//            next = num / 10;
//            ret += num % 10 + '0';
//            it1++;
//            it2++;
//        }
//
//        while (it1 != s.rend())
//        {
//            int num = *it1 - '0' + next;
//            next = num / 10;
//            ret += num % 10 + '0';
//            it1++;
//        }
//
//        while (it2 != t.rend())
//        {
//            int num = *it2 - '0' + next;
//            next = num / 10;
//            ret += num % 10 + '0';
//            it2++;
//        }
//
//        if (next)
//        {
//            ret += next + '0';
//        }
//        reverse(ret.begin(), ret.end());
//
//        return ret;
//    }
//};

//简化
//class Solution {
//public:
//    string solve(string s, string t) {
//        string ret;
//        int i = s.size() - 1, j = t.size() - 1;
//        int tmp = 0;
//        while (i >= 0 || j >= 0 || tmp)
//        {
//            if (i >= 0)
//                tmp += s[i--] - '0';
//            if (j >= 0)
//                tmp += t[j--] - '0';
//            ret += tmp % 10 + '0';
//            tmp /= 10;
//        }
//
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//};


//链表相加(二)
//https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=196&tqId=37147&ru=/exam/oj

//struct ListNode {
//    int val;
//    struct ListNode *next;
//    ListNode(int x)
//        : val(x)
//        , next(nullptr)
//    {}
//};
 
//#include<list>
//
//class Solution {
//public:
//
//    ListNode* addInList(ListNode* head1, ListNode* head2) {
//        list<int> l1, l2, ret;
//        while (head1 != nullptr)
//        {
//            l1.push_back(head1->val);
//            head1 = head1->next;
//        }
//        while (head2 != nullptr)
//        {
//            l2.push_back(head2->val);
//            head2 = head2->next;
//        }
//
//        auto it1 = l1.rbegin(), it2 = l2.rbegin();
//        int next = 0;
//
//        while (it1 != l1.rend() && it2 != l2.rend())
//        {
//            int num1 = *it1, num2 = *it2;
//            int num = num1 + num2 + next;
//            next = num / 10;
//            ret.push_front(num % 10);
//            it1++;
//            it2++;
//        }
//
//        while (it1 != l1.rend())
//        {
//            int num = *it1 + next;
//            next = num / 10;
//            ret.push_front(num % 10);
//            it1++;
//        }
//    
//        while (it2 != l2.rend())
//        {
//            int num = *it2 + next;
//            next = num / 10;
//            ret.push_front(num % 10);
//            it2++;
//        }
//
//        if (next)
//            ret.push_front(next);
//
//        ListNode* retL = nullptr;
//        ListNode* prev = nullptr;
//        ListNode* cur = retL;
//
//        for (auto num : ret)
//        {
//            if (retL == nullptr)
//            {
//                retL = new ListNode(num);
//                prev = retL;
//                ListNode* cur = retL->next;
//            }
//            else
//            {
//                cur = new ListNode(num);
//                if (prev != nullptr)
//                    prev->next = cur;
//                prev = cur;
//                cur = cur->next;
//            }
//        }
//        return retL;
//    }
//};

//简化
//class Solution {
//public:
//    // 逆序链表
//    ListNode* reverse(ListNode* cur)
//    {
//        ListNode* newnode = new ListNode(0);
//        while (cur)
//        {
//            ListNode* next = cur->next;
//            cur->next = newnode->next;
//            newnode->next = cur;
//            cur = next;
//        }
//        cur = newnode->next;
//        delete newnode;
//        return cur;
//    }
//
//    ListNode* addInList(ListNode* head1, ListNode* head2) {
//        // 逆序链表
//        head1=reverse(head1);
//        head2=reverse(head2);
//
//        ListNode* head = new ListNode(0);
//        ListNode* cur = head;
//        ListNode* cur1 = head1, * cur2 = head2;
//        int tmp = 0;
//        while (cur1 || cur2 || tmp)
//        {
//            if (cur1)
//            {
//                tmp += cur1->val;
//                cur1 = cur1->next;
//            }
//            if (cur2)
//            {
//                tmp += cur2->val;
//                cur2 = cur2->next;
//            }
//            cur->next = new ListNode(tmp % 10);
//            cur = cur->next;
//
//            tmp /= 10;
//        }
//        ListNode* ret = head->next;
//        delete head;
//
//        return reverse(ret);
//    }
//};


//NC10 大数乘法
//https://www.nowcoder.com/practice/c4c488d4d40d4c4e9824c3650f7d5571?tpId=196&tqId=37177&ru=/exam/oj


//class Solution {
//public:
//    string add(string& s, string& t) 
//    {
//        string ret;
//        auto it1 = s.rbegin(), it2 = t.rbegin();
//
//        int next = 0;
//        while (it1 != s.rend() && it2 != t.rend())
//        {
//            int num1 = *it1 - '0', num2 = *it2 - '0';
//            int num = num1 + num2 + next;
//            next = num / 10;
//            ret += num % 10 + '0';
//            it1++;
//            it2++;
//        }
//
//        while (it1 != s.rend())
//        {
//            int num = *it1 - '0' + next;
//            next = num / 10;
//            ret += num % 10 + '0';
//            it1++;
//        }
//
//        while (it2 != t.rend())
//        {
//            int num = *it2 - '0' + next;
//            next = num / 10;
//            ret += num % 10 + '0';
//            it2++;
//        }
//
//        if (next)
//        {
//            ret += next + '0';
//        }
//        reverse(ret.begin(), ret.end());
//
//        return ret;
//    }
//
//    string mult(int x, string& t, int index)
//    {
//        auto it = t.rbegin();
//        int next = 0;
//        string ret;
//        while (it != t.rend())
//        {
//            int num = (*it - '0') * x + next;
//            next = num / 10;
//            ret += num % 10 + '0';
//            it++;
//        }
//        if (next)
//            ret += next + '0';
//
//        reverse(ret.begin(), ret.end());
//        while (index--)
//        {
//            ret += '0';
//        }
//
//        return ret;
//    }
//
//    string solve(string s, string t) 
//    {
//        auto it1 = s.rbegin(), it2 = t.rbegin();
//        int index = 0;
//        vector<string> vs;
//        while (it1 != s.rend())
//        {
//            int num = *it1 - '0';
//            vs.push_back(mult(num, t, index));
//            it1++;
//            index++;
//        }
//
//        string ret = "0";
//        for (auto str : vs)
//        {
//            ret = add(ret, str);
//        }
//        int flag = 0;
//        for (auto ch : ret)
//        {
//            if (ch != '0')
//                flag = 1;
//        }
//        if (flag == 0)
//            ret = "0";
//        return ret;
//    }
//};
//
//
//int main()
//{
//    string s1, s2;
//    cin >> s1 >> s2;
//    Solution s;
//    cout << s.solve(s1, s2);
//}


//简化
//先计算⽆进位相乘并且相加后的结果；
//然后再处理进位。

//class Solution {
//public:
//    string solve(string s, string t) 
//    {
//        reverse(s.begin(), s.end());
//        reverse(t.begin(), t.end());
//        int m = s.size(),n = t.size();
//        vector<int> tmp(m + n);
//
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                tmp[i + j] += (s[i] - '0') * (t[j] - '0');
//            }
//        }
//
//        int num = 0;
//        string ret;
//        for (auto x : tmp)
//        {
//            num += x;
//            ret += num % 10 + '0';
//            num /= 10;
//        }
//
//        while (num)
//        {
//            ret += num % 10 + '0';
//            num /= 10;
//        }
//
//        while (ret.size() > 1 && ret.back() == '0') 
//            ret.pop_back();
//
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//};

//int main()
//{
//    Solution s;
//    s.solve("11", "22");
//}
